#include<stdio.h>
/* 二分查找(要求数组必须有序):
 * 递归：在调用一个函数的过程中又出现直接或间接的调用该函数本身。
 * 特征：
 * 1、可以把要解决的问题转化为新的问题，新问题的解决方法与原来相同，这是规模有规律的递减；
 * 2、每个子问题必须比原问题的规模更小，如果能够迅速减小更好；
 * 3、必须有一个明确的结束递归的条件；
 * 常用场景：欲知N须知N-1，欲知N-1须知N-2...预知2须知1，1的结果明确可知。
 * 经典实例：1、阶乘；2、斐波拉契数列
 */

int search(int arr[], int low, int high, int key){	
	int mid = (high + low)/2;
	while(low <= high){
		if(arr[mid]==key){
			return mid;	
		}else if(arr[mid]>key){
			return search(arr,low,mid-1,key);
		}else{
			return search(arr,mid+1,high,key);
		}
	}

	return -1;
}

int main()
{
	int arr[] = {1,3,5,7,9,11,13,15,17,19};
	int key = 10;
	int ret = search(arr,0,9,key);
	printf("查找元素的位置为:%d",ret);
	return 0;
}
